A. Field of the Invention
The present invention relates to an information match scheme and apparatus capable of providing Don""t Care Bits for searching information in a digital information system, especially to a bit-stream ternary match scheme and apparatus capable of flexibly adjusting the design parameters according to the concern of cost, performance and power consumption.
B. Description of the Prior Art
The technology of digital information search has been widely applied in the area which requires large data storage and processing. The search speed and its correctness depend on the algorithm applied. The vigorous growth of Internet services and applications has made the search mechanism in large search pool and database systems more demanding. Apparently, the conventional exact match has been insufficient for such purposes. For the new search environment and applications, the technology of ternary match scheme has become the choice for the digital information search of next generation. Currently, the bit-stream ternary match scheme technology can be widely applied in the area, such as IP routing, packet flow classification, packet content-sensitive flow classification, and security system.
The difference between the ternary match scheme and the conventional exact match scheme is that it provides an additional xe2x80x9cDon""t Care bitxe2x80x9d for the bit matching in addition to xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d. The xe2x80x9cDon""t Care Bitxe2x80x9d is immune to the match results of xe2x80x9c0xe2x80x9d or xe2x80x9c1xe2x80x9d. With reference to FIG. 1, in a ternary bit-stream 11, each bit can be xe2x80x9c1xe2x80x9d, xe2x80x9c1xe2x80x9d or xe2x80x9cXxe2x80x9d , which respectively represent the bit value matches with xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d or xe2x80x9cXxe2x80x9d (either of them). In practical application, the value of two bits can be represented by one bit, i.e., 00xe2x86x920, 01xe2x86x921, 10xe2x86x92X or 11xe2x86x92X.
In general, the bit-stream ternary match scheme can be illustrated in FIG. 2 which includes: a rule table 21 hand an information table 22. The procedure of the match scheme is as follows: first, input a match information 23 consisting of a bit-stream. Then, perform a ternary match between the match information 23 and the entries of the rule table 21. Finally, determine if there is a hit according to the match result. If not, it indicates that there is no hit in the rule table 21. If yes, use the sequence number of the rule (rule ID) matched in the rule table 21 as an index to lookup the information table 22.
Refer to FIG. 3 for showing the format of the rule table 21. Each rule table 21 contains multiple rules. And each rule consists of a ternary bit-stream. The size of the rule table 21 is defined according to the maximum allowable length of the rules (W-bit) and the maximum number of rules (L). Each rule has a piece of correspondent information stored in the information table 22. The sequence of each piece of information in the information table 22 is correspondent to the sequence of the rules in the rule table 21. In that case, the number of the pieces of information stored in the information table 22 is also L. The sequence of the rules in the rule table 21 is arranged according to its priority order. The priority decreases as the rule ID number increases. For this reason, when there are more than two rules matched with the information in the information table 21, the rule ID with the highest priority will be selected.
However, the bottleneck for the current bit-stream ternary match scheme is that it cannot flexibly adjust the design parameters and search speed according to the concern of cost. Consequently, the cost/performance issue for implementing the bit-stream ternary match scheme and increasing the search speed is very high for large search spool and database systems.
Accordingly, it is an object of the present invention to provide a method and apparatus for bit-stream ternary match scheme with design flexibility, thereby to speed up the search in constant time.
It is another object of the present information to provide a method and apparatus for bit-stream ternary match scheme which can flexibly adjust the design parameters according to the concern of cost, performance, and power consumption, thereby to meet the requirement of different needs.
Accordingly, it is an aspect of the present invention to provide an apparatus for bit-stream ternary match scheme. The apparatus of the invention includes: multiple memory tables and equal number of corresponding selectors, a product module, and a priority encoder. Each memory table includes multiple memory banks. After the match information is input to the ternary match module, it is divided into several sub-bit-streams. Then, each sub-bit-stream is input to a correspondent selector for obtaining the content of a selected memory bank. The content of the memory bank contains the bit-streams after pre-computation procedure. Then, the output of each selector is forwarded to the product module to compute an unencoded match result. Finally, the unencoded match result is forwarded to the priority encoder for generating the encoded match result and match flag. If the match flag is negative, it indicates that there is no match between the match information and the rule table. If the result is positive, the encoded match result serves as an index for looking up the information table.
In an aspect of the present invention, a method for bit-stream ternary match scheme is provided. The method includes the steps of: (a) Determine the space of a rule table according to a maximum allowable bit-length (W) of a rule, and the number of maximum allowable rules (L). (b) Divide the maximum allowable bit-length (W) into N+1 sub-bit-streams, where N is an integer. (c) Determine N+1 memory tables and N+1 selectors according to the number of sub-bit-streams of the step (b). (d) Determine the scale of each memory table and each selector according the bit-length of correspondent sub-bit-stream of the step (b). (e) Encode a plurality of rules according to a pre-computation procedure and generate a plurality of encoded entries. (f) Sequentially store the plurality of encoded entries in the rule table. (g) Send the output of each of the N+1 selectors into a product module to compute an unencoded match result in response to match information. (h) Forward the unencoded match result of the product module to a priority encoder to perform priority encoding and generate an encoded match result and a match flag. And (i) determine if there is a match information existed according to the match flag. When the match flag indicates a negative result, there is no match between said match information and the rule table. On the other hand, when the match flag indicates a positive result, the encoded match result acts as an index for searching the information table.
According to the concern of cost, performance and power consumption, the present invention can be more flexible to divide the execution steps into several stages following the pipeline technology. Thus, the design parameters can be flexibly adjusted. Eventually, the throughput can be efficiently improved, thereby to reduce the power consumption. Moreover, the present invention can largely reduce the search time into constant time and save the cost according to a desirable performance.
Further scope of the applicability of the present invention will become apparent from the detailed description given hereinafter. However, it should be understood that the detailed description and specific examples, while indicating preferred embodiments of the invention, are given by way of illustration only, since various changes and modifications within the spirit and scope of the invention will become apparent to those skilled in the art from this detailed description.
These and other objects and advantages of the present invention will become apparent by reference to the following description and accompanying drawings, which are given by way of illustration only, and thus are not limitative of the present invention, and wherein:
FIG. 1 is a schematic diagram showing a conventional ternary bit-stream.
FIG. 2 is a schematic diagram showing the conventional bit-stream ternary match scheme.
FIG. 3 is a schematic diagram showing the rule table of the bit-stream ternary match scheme.
FIG. 4A is a schematic diagram showing the 1-rulexc3x971-bit bit-stream ternary match scheme according to a preferred embodiment of the present invention.
FIG. 4B is a schematic diagram showing the transformation table of the embodiment illustrated in FIG. 4A for converting the rules into the rule table.
FIG. 4C is a schematic diagram showing the 1-rulexc3x971-bit bit-stream ternary match scheme according to another preferred embodiment of the present invention.
FIG. 5A is a schematic diagram showing the 1-rulexc3x972-bit bit-stream ternary match scheme according to another preferred embodiment of the present invention.
FIG. 5B is a schematic diagram showing the transformation table of FIG. 5A for converting the rules into the rule table according to another preferred embodiment of the present invention.
FIG. 6 is a schematic diagram showing the 1-rulexc3x97W-bit bit-stream ternary match scheme according to another preferred embodiment of the present invention.
FIG. 7 is a schematic diagram showing the simplified 1-rulexc3x97W-bit ternary match scheme according to another preferred embodiment of the present invention for the concern of cost and performance.
FIG. 8 is a schematic diagram showing the 2-rulexc3x97W-bit bit-stream ternary match scheme according to another preferred embodiment of the present invention.
FIG. 9A is a schematic diagram showing the bit-stream ternary match scheme according to another preferred embodiment of the present invention.
FIG. 9B is a schematic diagram showing the product module of the embodiment as illustrated in FIG. 9A.
FIG. 10A is a schematic diagram showing the simplified bit-stream ternary match scheme according to another preferred embodiment of the present invention following the pipeline architecture for the concern of cost and performance.
FIG. 10B is a schematic diagram showing the structure of the Priority Encoder of FIG. 10A.
FIG. 10C is a schematic diagram showing the structure of the Product Module of FIG. 10C.